import java.util.Arrays;

public class ClimbStairs {

    public int climbStairs(int n) {
        int[] dp = new int[n + 1];
        Arrays.fill(dp, -1);
        return process(n, dp);
    }

    public int process(int n, int[] dp) {
        if (dp[n] != -1) return dp[n];
        if (n == 0) {
            dp[n] = 1;
        } else if (n == 1) {
            dp[n] = process(0, dp);
        } else {
            dp[n] = process(n - 1, dp) + process(n - 2, dp);
        }
        return dp[n];
    }
}
